import collections


class Solution(object):
    def smallestStringWithSwaps(self, s, pairs):
        n = len(s)
        p = [i for i in range(n)]

        def find(x):
            if x == p[x]:
                return x
            else:
                p[x] = find(p[x])
                return p[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                if rootx < rooty:
                    p[rooty] = rootx
                else:
                    p[rootx] = rooty

        for x, y in pairs:
            union(x, y)

        c_list = collections.defaultdict(list)
        index_list = collections.defaultdict(list)
        for x in range(n):
            rootx = find(x)
            c_list[rootx].append(s[x])
            index_list[rootx].append(x)
        out = [''] * n
        for key in c_list:
            c_list[key].sort()
            index_list[key].sort()
            for i in range(len(c_list[key])):
                out[index_list[key][i]] = c_list[key][i]
        return ''.join(out)


data = Solution()
s = "dcab"
pairs = [[0, 3], [1, 2]]
print(data.smallestStringWithSwaps(s, pairs))
